---
layout: post
title: Minibus stochastic process
date: '2014-11-23T14:57:00.001-08:00'
author: Alex Rogozhnikov
tags:
- Branching process
- Minibus process
modified_time: '2014-11-23T14:57:27.805-08:00'
blogger_id: tag:blogger.com,1999:blog-307916792578626510.post-8326490379402722620
blogger_orig_url: http://brilliantlywrong.blogspot.com/2014/11/minibus-stochastic-process-part-1.html
---

<p>
    Recently I had a talk in Pereslavl',
    so I needed to get up early and travel to bus station, because the only way to get to Pereslavl' on public transport
    is by intercity bus.
</p>
<p>
    That was a long way (about 6 hours one direction). But first step was to get to the nearest underground station,
    which is not so trivial in mornings.
    People hurry, traffic jams make public transport circulate slowly, and as a result,
    there is crowding in nearly every bus/minibus moving towards city center or nearest underground station.
</p>
<p>
    After I found a place for me in one of minibuses I was quite sure that there is at most free place for one or two
    passengers.
</p>
<p>
    Of course, I was wrong.
    The minibus was moving its way and driver skipped the stops if nobody wanted to get off, since minibus was already
    filled.
    But when he stopped and one of passengers got off, two new were coming into, which made it even more crowdy inside.
</p>
<p>
    Each time I was sure, that after looking inside people
    won't enter the minibus, and each time they did. Exactly two new passengers, others didn't dare.
</p>
<p>
    So I came up with such a simple stochastic process:
    <br/>
    At $t=0$ there is only one passenger.
    During small time interval $\Delta t$ each passenger with probability&nbsp;$\alpha \Delta t$ wants to get off.
    When he gets off, two new passengers are entering the bus.
</p>
<p>
<h3>Studying the <a href="http://en.wikipedia.org/wiki/Probability-generating_function">probability-generating
    function</a>
</h3>
<p>
    Let's
    introduce an analytical over $s$ function that will describe the process:<br/>$F(t, s) = \sum_{n=0}^{+\infty} p_n
    (t) s^n$, where $p_n(t)$ is probability that at the moment $t$ there are exactly $n$ passengers.
</p>
<p>
    Note:
</p>
<ol>
    <li>$F(t,1) = 1$ for any $t$, since the probabilities sum up to 1.</li>
    <li>$F(0,s) = s$, since initially there was exactly one passenger</li>
</ol>
<p>
    Now let's think about how this system evolves. During small time interval $\Delta t$ with probability $\alpha n
    \Delta t$ the number of passengers is incremented (by one).
</p>
<p>This is mathematically written as:</p>
<p>$$p_n(t + \Delta t) \cong p_n(t) + \alpha (n-1) \Delta t p_{n-1}(t) - \alpha n \Delta t p_{n}(t),
    \quad p_0 \equiv 0$$
</p>
<p>Which in the limit $\Delta t \to 0$ turns into the system of ODEs:</p>
<p>$$\frac{d}{dt} p_n(t) = - \alpha n p_{n}(t) + \alpha (n-1) p_{n-1}(t), \quad p_0 \equiv 0$$</p>
<p>Or equivalently this can be written as a single PDE:
    $$F_t(t,s) = \alpha F_s(t,s) (s^2 - s) $$</p>
<p>The last one is solved in a typical way:
    $$F=F(z), \quad z=e^{-\alpha t}\frac{s}{1-s}$$</p>
<p>So we can compute value for any $t,s$ by
    $$F(t,s) = F(0,s_0), \text{where } \; e^0 \frac{s_0}{1-s_0} = z = e^{-\alpha t}\frac{s}{1-s}, $$</p>
<p>and it is now easy to compute that
    $$s_0 = \frac{1}{1 + e^{\alpha t} \frac{1 - s}{s} }, $$</p>
<p>so for our setting with one passenger at $t=0$:
    $$F(t,s) = s_0 = \frac{1}{1 + e^{\alpha t} \frac{1 - s}{s} } = \frac{s e^{-\alpha t}}{1 -
    s(1 - e^{-\alpha t}) } $$
</p>
<p>and we can see that at moment $t$ this is <a href="http://en.wikipedia.org/wiki/Geometric_distribution">geometric
    distribution</a>
    with mean=$e^{\alpha t}$.
</p>
<p>As an example to play with, you can try to repeat the same for the process where a man is leaving the minibus
    and nobody comes in (so that is like fermion version of the same problem :) )
</p>
<p>You'd get
    $$F_t(t,s) = \alpha F_s(t,s) (1 - s) $$
    $$F_t(t,s) = s e^{-\alpha t} + (1 - e^{-\alpha t}) $$
</p>
<p>For the version with $k$ new passengers one would have the following PDE:
    $$F_t(t,s) = \alpha F_s(t,s) (s^k - s), $$</p>
<p>which is studied the same way</p>

<p><b>NB</b>: Easy to see that $F_t(t,1) = \text{const} $, which is good sign (probabilities always sum up to 1),
    and a simple self-check.
</p>
<p>First I solved this problem, then thought about possible applications and googled them.</p>
<p>The interesting thing that such systems form quite popular topic in statistics: they are called 'branching
    processes'.
</p>
<p>What is it in general case, and what are applications of such mad model — in the next part.</p>